
package ACM;

public class mergeSort {
    public mergeSort() {
    }

    public static void main(String[] args) {
        int[] q = new int[]{6, 2, 7, 34, 16, 15};
        q = merge_sort(q, 0, q.length - 1);

        for(int i = 0; i < q.length; ++i) {
            System.out.print(q[i] + " ");
        }

    }

    public static int[] merge_sort(int[] q, int l, int r) {
        if (l >= r) {
            return null;
        } else {
            int mid = l + r >> 1;
            merge_sort(q, l, mid);
            merge_sort(q, mid + 1, r);
            int k = 0;
            int i = l;
            int j = mid + 1;
            int[] tmp = new int[q.length];

            while(i <= mid && j <= r) {
                if (q[i] <= q[j]) {
                    tmp[k++] = q[i++];
                } else {
                    tmp[k++] = q[j++];
                }
            }

            while(i <= mid) {
                tmp[k++] = q[i++];
            }

            while(j <= r) {
                tmp[k++] = q[j++];
            }

            i = l;

            for(int var9 = 0; i <= r; ++var9) {
                q[i] = tmp[var9];
                ++i;
            }

            return q;
        }
    }
}
